#define _CRT_SECURE_NO_WARNINGS


//class Solution {
//public:
//    int triangleNumber(vector<int>& nums)
//    {
//        sort(nums.begin(), nums.end());
//        int sum = 0;
//        int n = nums.size();
//        for (int i = n - 1; i >= 2; i--)
//        {
//            int left = 0;
//            int right = i - 1;
//            while (left < right)
//            {
//                if (nums[left] + nums[right] > nums[i])
//                {
//                    sum += right - left;
//                    right--;
//                }
//                else
//                {
//                    left++;
//                }
//            }
//        }
//        return sum;
//    }
//};
//
//class Solution {
//public:
//    vector<vector<int>> threeSum(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        vector<vector<int>> ans;
//        int n = nums.size();
//        for (int end = n - 1; end >= 2; end--)
//        {
//            int left = 0;
//            int right = end - 1;
//            while (left < right)
//            {
//                int sum = nums[left] + nums[right] + nums[end];
//                if (sum == 0)
//                {
//                    ans.push_back({ nums[left],nums[right],nums[end] });
//                    while (left < right && nums[right] == nums[right - 1])
//                        right--;
//                    while (left < right && nums[left] == nums[left + 1])
//                        left++;
//
//                    left++;
//                    right--;
//                }
//                else if (sum > 0)
//                {
//                    right--;
//                }
//                else
//                {
//                    left++;
//                }
//            }
//            while (end >= 2 && nums[end] == nums[end - 1])
//                end--;
//        }
//        return ans;
//    }
//};
//
//
//class Solution {
//public:
//    vector<int> twoSum(vector<int>& price, int target) {
//        int left = 0;
//        int right = price.size() - 1;
//        while (left < right)
//        {
//            if (price[left] + price[right] > target)
//            {
//                right--;
//            }
//            else if (price[left] + price[right] < target)
//            {
//                left++;
//            }
//            else
//            {
//                return { price[left], price[right] };
//            }
//        }
//        return {};
//    }
//};

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;



class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        int n = nums.size();
        for (int end = n - 1; end >= 3; end--)
        {
            for (int endprev = end - 1; endprev >= 2; endprev--)
            {
                int left = 0;
                int right = endprev - 1;
                while (left < right)
                {
                    int sum = nums[end] + nums[endprev] + nums[left] + nums[right];
                    if (sum > target)
                    {
                        right--;
                    }
                    else if (sum < target)
                    {
                        left++;
                    }
                    else
                    {
                        ans.push_back({ nums[end],nums[endprev],nums[left],nums[right] });
                        while (left < right && nums[left] == nums[left + 1])
                            left++;
                        while (left < right && nums[right] == nums[right - 1])
                            right--;

                        left++;
                        right--;
                    }
                }
                while (endprev >= 2 && nums[endprev] == nums[endprev - 1])
                    endprev--;
            }
            while (end >= 3 && nums[end] == nums[end - 1])
                end--;
        }
        return ans;
    }
};

int main()
{
    vector<int> v({ 1,0,-1,0,-2,2 });
    Solution().fourSum(v,0);

    return 0;
}